CSE 373: Data Structures and Algorithms

Winter 2000

Programming Assignment 1 Due January 21, 2000

Please include your name and student id # on what you turn in. What you turn in must include a listing of the program, input data, and output data. As the deadline nears we will provide you with a set of sample input data.

The goal of this programming assignment is to learn some of the basic stack, queue, and linked list functions.

Write a program that implements a simple stack of integers and a queue of integers. The program must also implement a single accumulator for storing the results of a pop or dequeue operation. The program will take as input as input a file containing a list of simple commands. Every command starts on a new line

The commands are:

Command	Description
new stack of size <number>	Creates a new stack of size <number>, the previous stack is destroyed.
new queue of size <number>	Creates a new queue of size <number>, the previous queue is destroyed.
new linkedlist	Creates a new circular doubly linked list, the previous linked list is destroyed
dump stack	Dump the contents of the current stack include the stack size, top value, and contents between top and bottom.
dump queue	Dump the contents of the current queue from head to tail.
dump linkedlist	Dump the contents of the current linked list from front to back
push <number> | accumulator	Push either the specified <number> or the contents of the accumulator on the current stack if space is available.
top [operator]	If an operator is not specified then copy the top of the stack to the Accumulator, otherwise perform the operation specified between the contents of the Accumulator and the top of the stack. Valid operators are + - * /. Think of this as doing Accumulator = Top, Accumulator += Top, Accumulator -= Top, Accumulator *= Top, or Accumulator /= Top
pop [operator]	Like Top but also do a pop of the stack.
enqueue tail <number> | accumulator	Insert either the specified <number> or the accumulator to the tail of the queue.
enqueue head <number> | accumulator	Insert either the specified <number> or the accumulator to the head of the queue.
dequeue tail [operator]	Remove the tail of the queue and if an operator is not specified then put it in the accumulator, otherwise perform the operation and put the results in the accumulator. See Top description for a list of valid operators.
dequeue head [operator]	Like Dequeue tail but removes the head of the queue instead.
tail [operator]	Similar to Dequeue tail but leaves the queue intact.
head [operator]	Similar to Dequeue head but leaves the queue intact.
insert front <number> | accumulator	Insert either the specified <number> or the accumulator to the front of the linked list.
insert back <number> | accumulator	Insert either the specified <number> of the accumulator to the end of the linked list
remove front [operator]	Remove the front of the linked list and if an operator is not specified then put it in the accumulator otherwise perform the operation and put the results in the accumulator. See Top description for a list of valid operators.
remove back [operator]	Like Remove front but removes the back of the linked list instead
front [operator]	Similar to Remove front but leaves the linked list intact
back [operator]	Similar to Remove back but leaves the linked list intact

Sample input and output

Input	Output
new stack of size 10 new queue of size 10 push 1 enqueue tail 2 push 3 enqueue tail 4 push 5 enqueue head 6 top enqueue head accumulator dequeue tail push accumulator dump stack push 7 dump stack create stack 100 push 8 push 9 push 10 top pop + dump queue dump stack	dump of stack of size 10 stack[3] = 4 (top of stack) stack[2] = 5 stack[1] = 3 stack[0] = 1 dump of stack of size 10 stack[4] = 7 (top of stack) stack[3] = 4 stack[2] = 5 stack[1] = 3 stack[0] = 1 dump of queue of size 10 head to tail 5 6 2 dump of stack of size 100 stack[3] = 20 (top of stack) stack[2] = 10 stack[1] = 9 stack[0] = 8

More sample input and output

Input	Output
new stack of size 3 top push 1 push 2 push 3 push 4 push 5 pop pop pop pop pop	stack of size 3 “top” failed, stack empty stack of size 3 “push 4” failed, stack full stack of size 3 “push 5” failed, stack full stack of size 3 “pop” failed, stack empty stack of size 3 “pop” failed, stack empty

More sample input and output

Input	Output
new queue of size 2 tail head dequeue tail enqueue tail 1 enqueue tail 2 enqueue tail 3	queue of size 2 “tail” failed, queue empty queue of size 2 “head” failed, queue empty queue of size 2 “dequeue tail” failed, queue empty queue of size 2 “enqueue tail 3” failed, queue full

Extra Credit

Implement the following commands

Command	Description
reverse stack	Reverses all the entries in the stack
reverse queue	Reverses all the entries in the queue
reverse linkedlist	Reverses all the entries in the linked list
copy stack to queue	Copies the contents of the stack to the queue so that top of the stack is at the head of the queue and the bottom of the stack is at the tail of queue
copy stack to linkedlist	Copies the contents of the stack to the linked list so that the top of the stack is at the front of the linked list and the bottom of the stack is at the back of the linked list
copy queue to stack	Copies the contents of the queue to the stack such that the head of the queue is the top of the stack and the tail of the queue is the bottom of the stack.
copy queue to linkedlist	Copies the contents of the queue to the linked list such that the head of the queue is the front of the linked list and the tail of the queue is the back of the linked list
copy linkedlist to stack	Copies the contents of the linked list to the stack such that the front of the linked list is the top of the stack and the back of the linked list is the bottom of the stack
copy linkedlist to queue	Copies the contents of the linked list to the queue such that the front of the linked list is at the head of the queue and the back of the linked list is at the tail of the queue.